package sort.merge;

import sort.common.PrintArr;
import sort.common.SortClass;

/**
 * 归并排序
 */
public class MergeSort  extends PrintArr implements SortClass {


    @Override
    public void sort(int[] arr) {
        if(arr.length>0){
            int[] res = mergeSort(arr,0,arr.length -1);
            for (int i = 0; i < res.length; i++) {
                arr[i] = res[i];
            }
        }
    }

    //归并排序
    private int[] mergeSort(int[] arr,int startIndex,int endIndex){
        if (startIndex == endIndex){
            return new int[]{ arr[startIndex] };
        }else {
            int midIndex = (startIndex + endIndex)/2;
            //1.拆分
            int[] leftArr = mergeSort(arr,startIndex,midIndex);
            int[] rightArr = mergeSort(arr,midIndex+1,endIndex);

            //2.合并
            int i = 0,j = 0,k=0;
            int[] mergeArr = new int[leftArr.length + rightArr.length];
            while (i<leftArr.length && j<rightArr.length){
                if (leftArr[i]>rightArr[j]){
                    mergeArr[k++] = rightArr[j++];
                }else {
                    mergeArr[k++] = leftArr[i++];
                }
            }

            while (i<leftArr.length){
                mergeArr[k++] = leftArr[i++];
            }

            while (j<rightArr.length){
                mergeArr[k++] = rightArr[j++];
            }

            return mergeArr;
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 1, 5, 7, 11, 32, 43, 22, 15};
        MergeSort mergeSort = new MergeSort();
        mergeSort.sort(arr);
        mergeSort.printArr(arr);

        int[] ints = {3,2,1,0};
        int[] mergeCount = mergeSort.mergeCount(ints, 0, ints.length - 1);
        mergeSort.printArr(mergeCount);
        System.out.println("逆序对为:"+mergeSort.sum);
    }

    //利用归并排序求 数组中的 逆序对
    public int sum = 0;
    /**
     * 逆序对： 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对
     * 我们注意到在归并排序合并过程中，我们有一步判断：if(leftArr[i] > rightArr[j]) ,
     * 如果判断为真，那么显然，j 和 区间[i,middle]每一个点都形成逆序对，一共mid-i+1个（注意这里的mid要减去startIndex），
     * 而且只在这个地方会出现形成逆序对的情况，那么情况就很简单了，我们将原数组进行归并排序，
     * 并在if((leftArr[i] > rightArr[j] ) 为真的时候，统计一下逆序对的个数即可。
     * @return
     */
    public int[] mergeCount(int[] arr,int startIndex,int endIndex){
        if (startIndex == endIndex){
            return new int[]{ arr[startIndex] };
        }else {
            int midIndex = (startIndex + endIndex)/2;
            int[] leftArr = mergeCount(arr,startIndex,midIndex);
            int[] rightArr = mergeCount(arr,midIndex+1,endIndex);
            int[] mergeArr = new int[leftArr.length+rightArr.length];

            int i=0,j=0,k=0;
            while (i<leftArr.length&&j<rightArr.length){
                if (leftArr[i]>rightArr[j]){
                    mergeArr[k++] = rightArr[j++];

                    //此处统计逆序对个数 (注意这里要减去startIndex，因为i是从0起的)
                    sum += midIndex - startIndex + 1 -i;
                }else {
                    mergeArr[k++] = leftArr[i++];
                }
            }

            while (i<leftArr.length){
                mergeArr[k++] = leftArr[i++];
            }

            while (j<rightArr.length){
                mergeArr[k++] = rightArr[j++];
            }

            return mergeArr;
        }

    }
}
